1. Field of the Invention
The present invention relates to the field of general purpose lossless data compression based on block sorting. More specifically, the present invention relates to compression of sorted data representations obtained as a result of the Burrows-Wheeler Transform (BWT) [as described in M. Burrows, D. J. Wheeler, “A Block-Sorting Lossless Data Compression Algorithm”, Res. rept. 124, DIGITAL Systems Research Center, 1994], or the Sort Transform (ST) [described in M. Schindler, “A Fast Block-sorting Algorithm for Lossless Data Compression”, Proc. IEEE Data Compression Conference (DCC '97), pp. 469, 1997].
2. Background Discussion
Lossless compression is a process of obtaining economical representation of source information. Lossless compression methods are used in many areas, principally including data storage and data transmission. General-purpose lossless compression methods represent a universal approach to the problem. These methods are universal in terms of the kinds of data for which they are designed.
There are several approaches to the general-purpose lossless compression problem. One of the most efficient is block sorting compression first introduced by M. Burrows and D. J. Wheeler. The Burrows-Wheeler (BW) compression process consists of two stages: transform stage and encoding stage. In the first stage symbols of the original data block are permuted with the use of the Burrows-Wheeler Transform or its modification—the Sort Transform. In the both cases the symbols are put into an order determined by the lexicographic ordering of their contexts. High probability of coincidence of symbols occurring in similar contexts makes the new representation much more suitable for compression. In the second stage a dedicated lossless compression algorithm is sequentially (symbol-by-symbol) applied to the reordered (sorted) block to obtain a compressed data representation. Decompression becomes possible due to the reversibility of the transform and application of the zero-loss second stage compression algorithm.
Since the actual compression is performed in the second stage, one of the most important problems is finding an efficient compression method for sorted representations. Although sorted representations are convenient for compression, the best results are obtained with the use of nontrivial approaches.
There are two main approaches to compression of sorted representations. The first approach uses dynamic symbol ranking. Symbols are dynamically ranked using an appropriate rule. Typically, most recently processed symbols are assigned lower ranks During encoding (decoding) ranks, rather than symbols, are encoded (decoded) using various probabilistic methods. Rank encoding is frequently supplemented by run-length encoding as an efficient method of processing series of repeating symbols. The use of run-length encoding significantly reduces the computational complexity of an algorithm. Known ranking methods are: (1) Move-To-Front (MTF) [see M. Burrows, D. J. Wheeler, “A Block-Sorting Lossless Data Compression Algorithm”, Res. rept. 124, DIGITAL Systems Research Center, 1994; see also, B. Balkenhol, S. Kurtz, Y. M. Shtarkov, “Modifications of the Burrows and Wheeler Data Compression Algorithm”, Proc. IEEE Data Compression Conference (DCC '99), pp. 188-197, 1999]; (2) Inversion Frequencies (IF) [Z. Arnavut, S. S. Magliveras, “Block Sorting and Compression”, Proc. IEEE Data Compression Conference (DCC '97), pp. 181-190, 1997]; (3) Distance Coding (DC) [E. Binder, “Distance Coder”, comp. compression, 2000]; (4) Time Stamp (TS) [see, S. Albers, “Improved randomized on-line algorithms for the list update problem”, Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 412-419, 1995; see also, S. Albers, M. Mitzenmacher, “Average Case Analyses of List Update Algorithms, with Applications to Data Compression”, Algorithmica, vol. 21, no. 3, pp. 312-329, 1998]; (5) Weighted Frequency Count (WFC) [see, S. Deorowicz, “Improvements to Burrows-Wheeler compression algorithm”, Software—Practice and Experience, vol. 30, no. 13, pp. 1465-1483, 2000; see also, S. Deorowicz, “Second step algorithms in the Burrows-Wheeler compression algorithm”, Software-Practice and Experience, vol. 32, no. 2, pp. 99-111, 2002]; and (6) QLFC [F. Ghido, “QLFC—A Compression Algorithm Using the Burrows-Wheeler Transform”, Proc. IEEE Data Compression Conference (DCC '05), pp. 459, 2005].
An alternative approach implies using complicated adaptive probabilistic modeling in the symbol domain. In this technique, the probability of a symbol's appearance is estimated using the statistics of symbol appearances in already processed data. Most advanced technologies use binary context-based probabilistic models. Code is usually generated with the use of arithmetic encoding. There are many practical efforts currently being made in this direction. Although some projects are open source, no specific algorithms or unique methods have been publicly introduced (i.e., described in papers or patents).
Solutions of the first type use an indirect approach to information modeling in which the specifics of the original data are replaced by the rank specifics. Such an approach, although having several advantages, makes modeling less effective and results in larger encoded data sizes.
Although there were no efforts to properly expose the original ideas behind existing direct probabilistic methods, according to the information derived from open sources, existing algorithms that use this approach, especially those using binary oriented modeling, are impractical and unacceptable in many situations because of their extremely high computational complexity. Accordingly, it is desirable to have a new method of compressing sorted data presentations that outperforms known methods.
Certain portions of the detailed description set out below employ algorithms, arithmetic, or other symbolic representations of operations performed on data stored within a computing system. The terminology and nomenclature employed are common among those with skill in the art to communicate the substance of their understanding to others similarly skilled and knowledgeable. It will be understood that the operations discussed are performed on electrical and/or magnetic signals stored or capable of being stored, as bits, data, values, characters, elements, symbols, characters, terms, numbers, and the like, within the computer system processors, memory, registers, or other information storage, transmission, or display devices. The operations, actions or processes involve the transformation of physical electronic and/or magnetic quantities within such storage, transmission, or display devices.